package everyday;

import java.util.HashMap;
import java.util.Map;

public class T1157 {


    class MajorityChecker {
        int[] arr;
        int max;

        public MajorityChecker(int[] arr) {
            this.arr = arr;
            for (int i = 0; i < arr.length; i++) {
                max = Math.max(max, arr[i]);
            }
        }
        public int query(int left, int right, int threshold) {
            int[] sum = new int[max + 1];
            for (int i = left; i <=right ; i++) {
                sum[arr[i]]++;
                if (sum[arr[i]]>=threshold)return arr[i];
            }
            return -1;
        }
    }
}
